import networkx as nx
import itertools
from config.parameter_carrier import ParameterCarrier
import numpy as np
from data_preparation.trajectory_set import TrajectorySet
from data_preparation.trajectory import Trajectory
from tools.noise import Noise
from tools.general_tools import GeneralTools
from discretization.divide import Divide
import copy as cop
import sys


class Grid:

    #
    def __init__(self, cc: ParameterCarrier):
        # give some parameter to grid
        self.north_border = -1
        self.south_border = -1
        self.west_border = -1
        self.east_border = -1
        self.cc = cc
        self.extend_ratio = 0.00001

        # this parameter gives all point numbers in the space
        self.whole_trajectory_set_point_number = 0
        self.trajectory_number = 0

        # these two parameters store the divide result
        self.x_divide_bins_array = np.array([])
        self.y_divide_bins_array = np.array([])

        self.level1_cell_index_to_row_col_array = np.array([])
        self.level1_cell_number = -1

        self.level1_cell_row_col_to_index_dict = {}

        # this parameter stores border of level1 'cell's, order is north, south, west, east
        self.level1_border = np.array([])

        # these two parameters store non-noisy and noisy version of grid density
        self.regularized_level1_grid_real_density = np.array([])  # 是整个数据集的网格出现频率（修正后）
        self.regularized_level2_grid_real_density = np.array([])  # 是二级网格的出现频率（修正后）
        self.level1_grid_noisy_density = np.array([])  # 是上面的加噪版
        self.level2_subdividing_parameter = np.array(
            [])  # 网格需要分裂的数量-> level1的加噪密度/initial_parameter=200 计算得出就是二级网格的数量109
        self.level2_index_by_level1_index_and_inner_row_col_index = np.array([])  # 二维数组
        self.level2_cell_outer_index_and_inner_row_col_to_index_dict = {}  # 将子网格索引数组（上面那个）转换为字典
        self.subcell_index_to_large_cell_index_dict = np.array([])  # 记录子网格属于哪个大网格
        self.level2_cell_borders = np.array([])  # 一个子网格的边界
        self.level2_x_bin_dict = []  # 是一个二维数组，第一维是第一层网格编号，第二层是这个网格的子网格的bin组
        self.level2_y_bin_dict = []
        self.subcell_number = -1  # 子网格数量
        self.subcell_neighbors_of_level1_index_and_inner_row_col = []
        self.subcell_neighbors_real_level2_index = []
        self.distance_network = nx.Graph()
        self.level_fisrt_node_value = np.array([])
        self.level_fisrt_node_value_noisy = np.array([])

    def give_level2_cell_border_by_index(self, index, north, south, west, east):
        self.level2_cell_borders[index, 0] = north
        self.level2_cell_borders[index, 1] = south
        self.level2_cell_borders[index, 2] = west
        self.level2_cell_borders[index, 3] = east

    def give_level2_cell_index_by_level1_index_and_inner_row_col_index(self, subcell_index, big_cell_index, x_index,
                                                                       y_index):
        self.level2_index_by_level1_index_and_inner_row_col_index[subcell_index, 0] = int(big_cell_index)
        self.level2_index_by_level1_index_and_inner_row_col_index[subcell_index, 1] = int(x_index)
        self.level2_index_by_level1_index_and_inner_row_col_index[subcell_index, 2] = int(y_index)

    def give_gird_border(self, value1: np.ndarray, direction1: str) -> None:
        if direction1 == 'n':
            self.north_border = value1
        elif direction1 == 's':
            self.south_border = value1
        elif direction1 == 'w':
            self.west_border = value1
        elif direction1 == 'e':
            self.south_border = value1
        elif direction1 == 'all':
            self.north_border = value1[0]
            self.south_border = value1[1]
            self.west_border = value1[2]
            self.east_border = value1[3]
        else:
            raise ValueError('wrong direction parameter')

    # this function get border of grid, configure side1 stands for which boder to give. 'n' for north, 's' for south,
    # 'w' for west and 'e' for east. if side1 is 'a', then it means to give out all sides of border in a nd array
    # with the order north, south, west, east
    def get_grid_border(self, direction1: str):
        if direction1 == 'n':
            border = self.north_border
        elif direction1 == 's':
            border = self.south_border
        elif direction1 == 'w':
            border = self.west_border
        elif direction1 == 'e':
            border = self.east_border
        elif direction1 == 'all':
            border = np.array([self.north_border, self.south_border, self.west_border, self.east_border])
        else:
            raise ValueError('wrong side parameter')
        return border

    def calculate_border(self, trajectory_set1: TrajectorySet) -> None:
        self.trajectory_number = trajectory_set1.trajectory_number
        extend_ratio1 = self.extend_ratio
        south1 = 1000000000
        north1 = -1000000000
        west1 = 1000000000
        east1 = -1000000000
        trajectory_number = trajectory_set1.trajectory_number
        for trajectory_index in range(trajectory_number):
            trajectory1 = trajectory_set1.give_trajectory_by_index(trajectory_index)
            arr = trajectory1.real_point_trajectory
            if west1 > np.amin(arr[:, 0]):
                west1 = np.amin(arr[:, 0])  # 找到数组第一列的最小值赋值给west1
            if east1 < np.amax(arr[:, 0]):
                east1 = np.max(arr[:, 0])
            if south1 > np.amin(arr[:, 1]):
                south1 = np.amin(arr[:, 1])
            if north1 < np.amax(arr[:, 1]):
                north1 = np.amax(arr[:, 1])
        x_extend = extend_ratio1 * (east1 - west1)
        west1 = west1 - x_extend
        east1 = east1 + x_extend
        y_extend = extend_ratio1 * (north1 - south1)
        south1 = south1 - y_extend
        north1 = north1 + y_extend
        border_1 = np.array([north1, south1, west1, east1])
        self.give_gird_border(border_1, direction1='all')
        print('网格边界:', border_1)

    # this function get point number of the whole dataset
    def calculate_point_number(self, trajectory_set1: TrajectorySet) -> None:
        self.whole_trajectory_set_point_number = trajectory_set1.get_trajectory_set_point_number()

    # 此函数为网格划分参数计算最佳的1级划分参数，
    # 输出为 array[x_divide_number, y_divide_number, x_increase, y_increase]
    def give_level1_divide_parameter(self):
        total_point_number = self.whole_trajectory_set_point_number
        all_border = self.get_grid_border('all')
        divide1 = Divide(self.cc)
        divide_level1_parameter_array = divide1.calculate_level1_divide_parameter(total_point_number,
                                                                                  self.trajectory_number, all_border)
        divide_number = divide_level1_parameter_array[0]
        return divide_number  # 返回x轴的划分参数

    # 该函数执行一级分割，即完全分割
    def level1_divide(self) -> None:
        divide_parameter = int(self.give_level1_divide_parameter())  # 返回的是x轴的划分数量
        tool1 = GeneralTools()
        x_start = self.get_grid_border('w')
        x_end = self.get_grid_border('e')
        x_divide_number = divide_parameter
        y_start = self.get_grid_border('s')
        y_end = self.get_grid_border('n')
        y_divide_number = divide_parameter
        x_divide_bins_array = tool1.get_bin(x_start, x_end, x_divide_number)
        y_divide_bins_array = tool1.get_bin(y_start, y_end, y_divide_number)
        self.x_divide_bins_array = x_divide_bins_array
        self.y_divide_bins_array = y_divide_bins_array
        cell_number = (x_divide_bins_array.size - 1) * (y_divide_bins_array.size - 1)
        self.level1_cell_number = cell_number

    # this function gives every cell border
    def set_cell_borders(self, x_divide_bins_array: np.ndarray, y_divide_bins_array: np.ndarray) -> None:
        row_number = y_divide_bins_array.size - 1
        column_number = x_divide_bins_array.size - 1
        cell_number = row_number * column_number
        leve1_cell_index_to_border_dict = np.empty((cell_number, 4))
        leve1_cell_index_to_border_dict.reshape((-1, 4))
        # index_border_dict创建一个数组，大小为cell_number*4，用于存储每个单元格的边界信息（北、南、西、东边界）
        level1_cell_index_to_row_col_dict = np.empty((cell_number, 2), dtype=int)
        level1_cell_index_to_row_col_dict.reshape((-1, 2))
        # index_position_dict用于存储每个单元格的位置信息（行索引和列索引）
        cell_counter = 0
        for x_index in range(column_number):
            for y_index in range(row_number):
                north_border = y_divide_bins_array[y_index + 1]
                south_border = y_divide_bins_array[y_index]
                west_border = x_divide_bins_array[x_index]
                east_border = x_divide_bins_array[x_index + 1]
                border_array = np.array([[north_border, south_border, west_border, east_border]])
                position_array = np.array([[x_index, y_index]])
                leve1_cell_index_to_border_dict[cell_counter] = border_array
                level1_cell_index_to_row_col_dict[cell_counter] = position_array
                cell_counter = cell_counter + 1
        # 将边界和位置信息赋值给类的属性：
        self.level1_border = leve1_cell_index_to_border_dict
        self.level1_cell_index_to_row_col_array = level1_cell_index_to_row_col_dict
        row_col_to_index_dict = self.set_row_col_to_index_dictionary()
        self.level1_cell_row_col_to_index_dict = row_col_to_index_dict

    # this function gives point array in trajectory the level1 cell index array
    def get_trajectory_point_level1_index(self, x_index_array: np.ndarray,
                                          y_index_array: np.ndarray) -> np.ndarray:
        y_bins = self.y_divide_bins_array
        x_bins = self.x_divide_bins_array
        y_bin_number = y_bins.size - 1
        index_array = x_index_array * y_bin_number + y_index_array
        return index_array  # 返回全局索引：（1，2）返回1*2+2=5

    # this function creates a dictionary of position-index of level 1 dividing
    def set_row_col_to_index_dictionary(self) -> dict:
        level1_cell_row_col_dict = self.level1_cell_index_to_row_col_array
        row_col_to_index_dict = {}
        for cell_index in range(level1_cell_row_col_dict.shape[0]):  # .shape[0] 表示行数
            row_index = level1_cell_row_col_dict[cell_index, 0]
            column_index = level1_cell_row_col_dict[cell_index, 1]
            position_tuple = (row_index, column_index)
            row_col_to_index_dict[position_tuple] = cell_index
        return row_col_to_index_dict

    # position_index_dict = {
    #     (0, 0): 0,  # 位置 (0, 0) 对应单元格0
    #     (0, 1): 1,  # 位置 (0, 1) 对应单元格1
    #     (1, 0): 2,  # 位置 (1, 0) 对应单元格2
    #     (1, 1): 3  # 位置 (1, 1) 对应单元格3
    # }

    # This function creates level1 cell for
    def level1_cells(self) -> None:
        x_divide_bins_array = self.x_divide_bins_array  # x_divide_bins是数组，是网格的线
        y_divide_bins_array = self.y_divide_bins_array
        self.set_cell_borders(x_divide_bins_array, y_divide_bins_array)

    # this function makes point array in trajectories become cell array
    def level1_trajectory_set_point_to_cell(self, trajectory_set1: TrajectorySet) -> None:
        trajectory_number = trajectory_set1.get_trajectory_number()
        for trajectory_index1 in range(trajectory_number):
            trajectory1 = trajectory_set1.give_trajectory_by_index(trajectory_index1)
            self.set_trajectory_level1_cell_array(trajectory1)

    # this function transforms point array in a single trajectory into cell index array
    def set_trajectory_level1_cell_array(self, trajectory1: Trajectory,
                                         illegal_index_process_method: str = 'error', interp=True) -> None:
        general_tool1 = GeneralTools()
        point_array = trajectory1.real_point_trajectory
        x_bin_array = self.x_divide_bins_array
        y_bin_array = self.y_divide_bins_array
        trajectory_level1_cell_row_col_array = general_tool1.get_points_bin_index(point_array, x_bin_array, y_bin_array)
        self.illegal_index_process(trajectory_level1_cell_row_col_array, illegal_index_process_method)
        # 判断是否有索引超出范围的点
        cell_index_array = self.get_trajectory_point_level1_index(trajectory_level1_cell_row_col_array[:, 1],
                                                                  trajectory_level1_cell_row_col_array[:, 0])
        # 返回全局索引：（1，2）返回1*2+2=5
        trajectory1.trajectory_level1_cell_index_array = cell_index_array

    # this function processes illegal index i.e. index out of bins
    # if processing type is 'error', then when the array is illegal, raise an error
    def illegal_index_process(self, index_array: np.ndarray, processing_type: str) -> None:
        illegal_x_point = index_array[:, 0] < 0
        illegal_y_point = index_array[:, 1] < 0
        if processing_type == 'error':
            if (illegal_x_point.any()) or (illegal_y_point.any()):
                raise ValueError('this discretion dose not allow out of bins')

    # this function calculates cell density of level1 dividing
    def level1_density(self, trajectory_set1: TrajectorySet) -> None:
        level1_cell_number = self.level1_cell_number
        density = np.zeros(level1_cell_number)
        trajectory_number = trajectory_set1.get_trajectory_number()
        for trajectory_index in range(trajectory_number):
            if trajectory_index >= trajectory_number:
                raise IndexError('wrong index'.format(trajectory_index))
            trajectory1 = trajectory_set1.give_trajectory_by_index(trajectory_index)
            frequency_array = trajectory1.give_regularized_trajectory_cell_density(level1_cell_number)
            # 返回一个大小为全体网格数量的数组，其中数组值表示这条轨迹在这个网格出现的归一化频率
            density = density + frequency_array  # density是整个数据集的网格出现归一化频率
        self.regularized_level1_grid_real_density = density

    # this function gives noisy frequency
    def noisy_frequency(self, epsilon_for_level1_density) -> None:
        real_density = self.regularized_level1_grid_real_density
        noise1 = Noise()
        sensitivity = 1
        noisy_density = noise1.add_laplace(real_density, epsilon_for_level1_density, sensitivity)
        # 返回加噪版本的频率
        self.level1_grid_noisy_density = noisy_density

    # this function calculates subdividing parameter for every level1 cell
    def level2_parameter(self) -> None:
        noisy_density = self.level1_grid_noisy_density
        # noisy_density = self.level1_grid_noisy_density
        level1_cell_number = noisy_density.size
        subdividing_parameter = np.zeros(level1_cell_number, dtype=int) + 1  # 存储每个单元格需要分裂的数量，初始值为1不分裂
        trajectory_number1 = self.trajectory_number
        threshold = trajectory_number1 * 0.05 / self.level1_cell_number
        # threshold = self.subdividing_threshold()
        level1_cell_need_to_subdivide = noisy_density > threshold  # 判断哪些网格需要分裂
        divide1 = Divide(self.cc)

        for cell_index in range(level1_cell_number):
            if level1_cell_need_to_subdivide[cell_index]:
                # subdividing_number = self.subdividing_number(noisy_density[cell_index])
                subdividing_number = divide1.subdividing_parameter(noisy_density[cell_index])
                subdividing_parameter[cell_index] = subdividing_number
        self.level2_subdividing_parameter = subdividing_parameter

    # this function calculate bins for subdividing
    def subdividing_bins(self, level1_cell_index: int, this_cell_subdividing_parameter: int):
        general_tool1 = GeneralTools()
        big_cell_border_dict = self.level1_border
        big_cell_border = big_cell_border_dict[level1_cell_index]
        big_cell_n = big_cell_border[0]
        big_cell_s = big_cell_border[1]
        big_cell_w = big_cell_border[2]
        big_cell_e = big_cell_border[3]
        this_cell_x_bin = general_tool1.get_bin(big_cell_w, big_cell_e, this_cell_subdividing_parameter)
        this_cell_y_bin = general_tool1.get_bin(big_cell_s, big_cell_n, this_cell_subdividing_parameter)
        self.level2_x_bin_dict.append(this_cell_x_bin)
        self.level2_y_bin_dict.append(this_cell_y_bin)

    def give_subcell_border(self, large_cell_index: int, subcell_index: int, subcell_inner_x_index: int,
                            subcell_inner_y_index: int):
        this_cell_x_bin = self.level2_x_bin_dict[large_cell_index]
        # 获得large_cell_index编号的网格的子网格的bin
        this_cell_y_bin = self.level2_y_bin_dict[large_cell_index]
        small_cell_w = this_cell_x_bin[subcell_inner_x_index]
        small_cell_e = this_cell_x_bin[subcell_inner_x_index + 1]
        small_cell_s = this_cell_y_bin[subcell_inner_y_index]
        small_cell_n = this_cell_y_bin[subcell_inner_y_index + 1]
        self.give_level2_cell_border_by_index(subcell_index, small_cell_n, small_cell_s, small_cell_w, small_cell_e)

    # this function subdivides cells that are too dense
    def subdividing(self):
        self.level2_parameter()  # 得到所有网格需要分裂的数量
        subdividing_parameter = self.level2_subdividing_parameter  # subdividing_parameter是数组，存储每个网格需要分裂的数量
        subdividing_cell_number = subdividing_parameter ** 2
        cell_number = np.sum(subdividing_cell_number)
        cell_number = int(cell_number)
        self.level2_cell_borders = np.empty((cell_number, 4))
        self.level2_index_by_level1_index_and_inner_row_col_index = np.empty((cell_number, 3), dtype=int)
        subcell_index = 0
        for level1_cell_index in range(self.level1_cell_number):  # subdividing_parameter.size还是一级网格的数量
            this_cell_subdividing_parameter = subdividing_parameter[level1_cell_index]
            self.subdividing_bins(level1_cell_index, this_cell_subdividing_parameter)  # 获得这个网格子网格的x和y的bin
            for subcell_inner_x_index in range(this_cell_subdividing_parameter):
                for subcell_inner_y_index in range(this_cell_subdividing_parameter):
                    self.give_subcell_border(level1_cell_index, subcell_index, subcell_inner_x_index,
                                             subcell_inner_y_index)  # 记录每个子网格的边界
                    self.give_level2_cell_index_by_level1_index_and_inner_row_col_index(subcell_index,
                                                                                        level1_cell_index,
                                                                                        subcell_inner_x_index,
                                                                                        subcell_inner_y_index)  # 记录每个子网格的索引
                    subcell_index = subcell_index + 1
        self.subcell_number = self.level2_index_by_level1_index_and_inner_row_col_index.shape[0]
        self.level2_position_to_index_dict()  # 将子网格索引数组转换为字典
        self.give_level2_subcell_belong_large_cell_dict()  # 记录子网格属于哪个大网格
        self.give_subcells_neighbors()

    # this function gives position to index dict of level2 cell
    def level2_position_to_index_dict(self):  # 将子网格索引数组转换为字典
        index_to_position_dict = self.level2_index_by_level1_index_and_inner_row_col_index  # 获得子网格的索引数组
        position_to_index_dict = {}

        for cell_index in range(self.subcell_number):
            position = (index_to_position_dict[cell_index, 0], index_to_position_dict[cell_index, 1],
                        index_to_position_dict[cell_index, 2])
            position_to_index_dict[position] = cell_index
        self.level2_cell_outer_index_and_inner_row_col_to_index_dict = position_to_index_dict

    #
    def give_level2_subcell_belong_large_cell_dict(self):
        index_to_position_dict = self.level2_index_by_level1_index_and_inner_row_col_index
        sub_number = self.subcell_number
        array = np.zeros(sub_number) - 1  # 创建一个大小为子网格数量的数组，初始值为-1
        for row_i in range(sub_number):
            array[row_i] = index_to_position_dict[row_i, 0]
        self.subcell_index_to_large_cell_index_dict = array  # 记录子网格属于哪个大网格

    # this function gives subcell number

    # this function gives all subcell neighbors
    def give_subcells_neighbors(self):
        subcell_number = self.subcell_number
        for subcell_index in range(subcell_number):
            neighbors = self.get_neighbor_of_i(subcell_index)
            self.subcell_neighbors_of_level1_index_and_inner_row_col.append(neighbors)
            # 邻居指的是上下左右
            # subcell_neighbors_position每个元素是二维数组，包含大单元格索引、x、y

    def construct_neighbors_real_level2_index(self):  # 将三维的邻居信息转换为一维索引
        positions = self.subcell_neighbors_of_level1_index_and_inner_row_col
        real_index = []  # 维度是subcell_number
        final_index = []
        for neighbor_position in positions:
            neighbor_number = neighbor_position.shape[0]
            index = np.empty(neighbor_number, dtype=int)
            for neighbor_index_of_this_subcell in range(neighbor_number):
                single_neighbor_position = neighbor_position[neighbor_index_of_this_subcell]
                neighbor_subcell_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[
                    tuple(single_neighbor_position)]
                index[neighbor_index_of_this_subcell] = int(neighbor_subcell_index)
            real_index.append(index)

        for subcell_index in range(len(real_index)):
            neighbor_indices_for_this_temp = real_index[subcell_index]
            neighbor_indices_for_this = np.unique(neighbor_indices_for_this_temp)
            if np.max(neighbor_indices_for_this) < 0:
                neighbor_indices_for_this = np.array([])
            else:
                neighbor_indices_for_this = neighbor_indices_for_this[neighbor_indices_for_this >= 0]
            final_index.append(neighbor_indices_for_this)
        self.subcell_neighbors_real_level2_index = final_index
        # print(self.subcell_neighbors_real_level2_index[119])
        # print(self.subcell_neighbors_real_level2_index[130])

    # this function gives subcell i neighbor subcells
    def get_neighbor_of_i(self, subcell_index):
        whole_position_of_i = self.level2_index_by_level1_index_and_inner_row_col_index[subcell_index]
        large_cell_index = whole_position_of_i[0]
        subdividing_parameter = self.level2_subdividing_parameter[large_cell_index]
        is_large_cell = False
        if subdividing_parameter <= 1:  # 如果这个网格不需要划分
            is_large_cell = True
        if is_large_cell:
            neighbors = self.neighbor_of_large_i_of_level1_index_and_inner_row_col(
                large_cell_index)  # 返回上下左右邻居，格式为(neighbor_level1_index, 0, 0)的形式
        else:
            x_in_large = whole_position_of_i[1]
            y_in_large = whole_position_of_i[2]
            neighbors = self.neighbor_of_subcell_i(large_cell_index, x_in_large, y_in_large)
        neighbors.astype(int)
        return neighbors

    # this function finds neighbors for a large cell
    def neighbor_of_large_i_of_level1_index_and_inner_row_col(self, large_index: int):
        gt1 = GeneralTools()
        level1_x_bins = self.x_divide_bins_array
        level1_y_bins = self.y_divide_bins_array
        large_neighbor_dict = self.get_adjacent_cells_row_col_dict(large_index, level1_x_bins, level1_y_bins)
        # 返回一个字典，key是方向，value是相邻的网格的索引
        # 这里只记录单元格上下左右的网格作为邻居
        neighbor_dict = gt1.transfer_neighbor_row_col_pair_to_index(large_neighbor_dict,
                                                                    self.level1_cell_row_col_to_index_dict)
        # 将邻居字典中的位置转为索引
        neighbors = []
        for direction_key in neighbor_dict:
            neighbor_level1_index = neighbor_dict[direction_key]
            if neighbor_level1_index is not False:
                this_large_cell_subdivide_parameter = self.level2_subdividing_parameter[neighbor_level1_index]
                whether_divided = False
                if this_large_cell_subdivide_parameter > 1:
                    whether_divided = True
                if whether_divided:
                    neighbor_subcells = self.subcell_neighbor_of_large_cell(neighbor_level1_index, direction_key)
                    neighbors = neighbors + neighbor_subcells
                else:
                    level2_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[
                        (neighbor_level1_index, 0, 0)]
                    # neighbors.append(level2_index)
                    neighbors.append(np.array([neighbor_level1_index, 0, 0]))
        # neighbors = np.array(neighbors, dtype=int)
        neighbors1 = np.empty((len(neighbors), 3))
        for row_i in range(len(neighbors)):
            neighbors1[row_i, :] = neighbors[row_i]
        return neighbors1

    # this function gives subcell neighbors of a large cell
    def subcell_neighbor_of_large_cell(self, neighborhood_cell_level1_index, neighborhood_direction):
        x_subbin = self.level2_x_bin_dict[neighborhood_cell_level1_index]
        y_subbin = self.level2_y_bin_dict[neighborhood_cell_level1_index]
        x_number = x_subbin.size - 1
        y_number = y_subbin.size - 1
        neighborhood_subcells_list = []
        if neighborhood_direction == 'w':
            for y_index in range(y_number):
                position_array = np.array([neighborhood_cell_level1_index, x_number - 1, y_index])
                neighborhood_subcells_list.append(position_array)
        if neighborhood_direction == 'e':
            for y_index in range(y_number):
                position_array = np.array([neighborhood_cell_level1_index, 0, y_index])
                neighborhood_subcells_list.append(position_array)
        if neighborhood_direction == 's':
            for x_index in range(x_number):
                position_array = np.array([neighborhood_cell_level1_index, x_index, y_number - 1])
                neighborhood_subcells_list.append(position_array)
        if neighborhood_direction == 'n':
            for x_index in range(x_number):
                position_array = np.array([neighborhood_cell_level1_index, x_index, 0])
                neighborhood_subcells_list.append(position_array)
        return neighborhood_subcells_list

    # this function finds neighbors for a subcell
    def neighbor_of_subcell_i(self, large_index, inner_x_position, inner_y_position):
        position = (large_index, inner_x_position, inner_y_position)
        this_subcell_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[position]
        x_bins = self.level2_x_bin_dict[large_index]
        y_bins = self.level2_y_bin_dict[large_index]
        x_number = x_bins.size - 1
        y_number = y_bins.size - 1
        # 北南西东
        # ture:代表哪个方向的邻居是大网格
        if inner_x_position == 0:
            if inner_y_position == 0:
                neighboring_direction = [False, True, True, False]
            elif inner_y_position == y_number - 1:
                neighboring_direction = [True, False, True, False]
            else:
                neighboring_direction = [False, False, True, False]
        elif inner_x_position == x_number - 1:
            if inner_y_position == 0:
                neighboring_direction = [False, True, False, True]
            elif inner_y_position == y_number - 1:
                neighboring_direction = [True, False, False, True]
            else:
                neighboring_direction = [False, False, False, True]
        else:
            if inner_y_position == 0:
                neighboring_direction = [False, True, False, False]
            elif inner_y_position == y_number - 1:
                neighboring_direction = [True, False, False, False]
            else:
                neighboring_direction = [False, False, False, False]

        neighbor_subcells = []
        large_cell_position_in_level1 = self.level1_cell_index_to_row_col_array[large_index]
        this_large_cell_level1_x = large_cell_position_in_level1[0]
        this_large_cell_level1_y = large_cell_position_in_level1[1]
        level1_x_divide_number = self.x_divide_bins_array.size - 1
        level1_y_divide_number = self.y_divide_bins_array.size - 1
        if neighboring_direction[0]:
            north_neighbor_large_y = this_large_cell_level1_y + 1
            neighbor_direction = 'n'
            if north_neighbor_large_y < level1_y_divide_number:
                north_neighbors = self.adjacent_subcells_of_a_subcell(
                    neighbor_direction, this_large_cell_level1_x, north_neighbor_large_y, this_subcell_index)
                neighbor_subcells = neighbor_subcells + north_neighbors
        if neighboring_direction[1]:
            south_large_neighbor_y = this_large_cell_level1_y - 1
            neighbor_direction = 's'
            if south_large_neighbor_y >= 0:
                south_neighbors = self.adjacent_subcells_of_a_subcell(
                    neighbor_direction, this_large_cell_level1_x, south_large_neighbor_y, this_subcell_index)
                neighbor_subcells = neighbor_subcells + south_neighbors
        if neighboring_direction[2]:
            west_large_neighbor_x = this_large_cell_level1_x - 1
            neighbor_direction = 'w'
            if west_large_neighbor_x >= 0:
                west_neighbors = self.adjacent_subcells_of_a_subcell(
                    neighbor_direction, west_large_neighbor_x, this_large_cell_level1_y, this_subcell_index)
                neighbor_subcells = neighbor_subcells + west_neighbors
        if neighboring_direction[3]:
            east_large_neighbor_x = this_large_cell_level1_x + 1
            neighbor_direction = 'e'
            if east_large_neighbor_x < level1_x_divide_number:
                east_neighbors = self.adjacent_subcells_of_a_subcell(
                    neighbor_direction, east_large_neighbor_x, this_large_cell_level1_y, this_subcell_index)
                neighbor_subcells = neighbor_subcells + east_neighbors
        # 处理内部小网格
        neighbor_subcells = neighbor_subcells \
                            + self.direct_neighbors_within_large_cell_of_subcell(x_number, large_index,
                                                                                 inner_x_position,
                                                                                 inner_y_position)

        neighbors = np.empty((len(neighbor_subcells), 3))
        for row_i in range(len(neighbor_subcells)):
            neighbors[row_i, :] = neighbor_subcells[row_i]

        return neighbors

    # this function gives direct four neighbors(top, bottom, left, right) of a subcell
    def direct_neighbors_within_large_cell_of_subcell(self, level2_divide_number, large_cell_index, inner_x_position,
                                                      inner_y_position):
        if inner_x_position - 1 >= 0:
            left_neighbor = np.array([large_cell_index, inner_x_position - 1, inner_y_position])
        else:
            left_neighbor = False
        if inner_x_position + 1 < level2_divide_number:
            right_neighbor = np.array([large_cell_index, inner_x_position + 1, inner_y_position])
        else:
            right_neighbor = False
        if inner_y_position + 1 < level2_divide_number:
            top_neighbor = np.array([large_cell_index, inner_x_position, inner_y_position + 1])
        else:
            top_neighbor = False
        if inner_y_position - 1 >= 0:
            bottom_neighbor = np.array([large_cell_index, inner_x_position, inner_y_position - 1])
        else:
            bottom_neighbor = False
        direct_neighbors = []
        if top_neighbor is not False:
            direct_neighbors.append(top_neighbor)
        if bottom_neighbor is not False:
            direct_neighbors.append(bottom_neighbor)
        if left_neighbor is not False:
            direct_neighbors.append(left_neighbor)
        if right_neighbor is not False:
            direct_neighbors.append(right_neighbor)
        return direct_neighbors

    # this function gives one side neighbors of a subcell.
    def adjacent_subcells_of_a_subcell(self, neighborhood_direction, large_neighbor_x, large_neighbor_y,
                                       this_subcell_index):
        this_border = self.level2_cell_borders[this_subcell_index]
        this_north = this_border[0]
        this_south = this_border[1]
        this_west = this_border[2]
        this_east = this_border[3]
        neighbor_large_cell_position = (large_neighbor_x, large_neighbor_y)
        neighborhood_cell_level1_index = self.level1_cell_row_col_to_index_dict[neighbor_large_cell_position]
        # neighbors = self.subcell_neighbor_of_large_cell(neighborhood_cell_level1_index, neighborhood_direction)
        # return neighbors

        x_subbin = self.level2_x_bin_dict[neighborhood_cell_level1_index]
        y_subbin = self.level2_y_bin_dict[neighborhood_cell_level1_index]
        x_number = x_subbin.size - 1
        y_number = y_subbin.size - 1
        neighborhood_subcells_list = []
        if neighborhood_direction == 'w':
            for y_index in range(y_number):
                position_array = np.array([neighborhood_cell_level1_index, x_number - 1, y_index])
                neighborhood_subcells_list = self.get_west_or_east_neighbor_of_subcell(this_subcell_index,
                                                                                       position_array,
                                                                                       neighborhood_subcells_list)
                # neighbor_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[tuple(position_array)]
                # border = self.level2_cell_borders[neighbor_index]
                # neighbor_north = border[0]
                # neighbor_south = border[1]
                # if neighbor_south <= this_south and neighbor_north >= this_north:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_south < this_south < neighbor_north:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_south < this_north < neighbor_north:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_south >= this_south and neighbor_north <= this_north:
                #     neighborhood_subcells_list.append(position_array)

        if neighborhood_direction == 'e':
            for y_index in range(y_number):
                position_array = np.array([neighborhood_cell_level1_index, 0, y_index])
                neighborhood_subcells_list = self.get_west_or_east_neighbor_of_subcell(this_subcell_index,
                                                                                       position_array,
                                                                                       neighborhood_subcells_list)
                # neighbor_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[tuple(position_array)]
                # border = self.level2_cell_borders[neighbor_index]
                # neighbor_north = border[0]
                # neighbor_south = border[1]
                # if neighbor_south <= this_south and neighbor_north >= this_north:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_south < this_south < neighbor_north:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_south < this_north < neighbor_north:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_south > this_south and neighbor_north < this_north:
                #     neighborhood_subcells_list.append(position_array)
        if neighborhood_direction == 's':
            for x_index in range(x_number):
                position_array = np.array([neighborhood_cell_level1_index, x_index, y_number - 1])
                neighborhood_subcells_list = self.get_north_or_south_neighbor_of_subcell(this_subcell_index,
                                                                                         position_array,
                                                                                         neighborhood_subcells_list)
                # neighbor_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[tuple(position_array)]
                # border = self.level2_cell_borders[neighbor_index]
                # neighbor_west = border[2]
                # neighbor_east = border[3]
                # if neighbor_west <= this_west and neighbor_east >= this_east:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_west < this_west < neighbor_east:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_west < this_east < neighbor_east:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_west > this_west and neighbor_east < this_east:
                #     neighborhood_subcells_list.append(position_array)
        if neighborhood_direction == 'n':
            for x_index in range(x_number):
                position_array = np.array([neighborhood_cell_level1_index, x_index, 0])
                neighborhood_subcells_list = self.get_north_or_south_neighbor_of_subcell(this_subcell_index,
                                                                                         position_array,
                                                                                         neighborhood_subcells_list)
                # neighbor_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[tuple(position_array)]
                # border = self.level2_cell_borders[neighbor_index]
                # neighbor_west = border[2]
                # neighbor_east = border[3]
                # if neighbor_west <= this_west and neighbor_east >= this_east:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_west < this_west < neighbor_east:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_west < this_east < neighbor_east:
                #     neighborhood_subcells_list.append(position_array)
                # elif neighbor_west > this_west and neighbor_east < this_east:
                #     neighborhood_subcells_list.append(position_array)
        return neighborhood_subcells_list

    def get_west_or_east_neighbor_of_subcell(self, this_subcell_index, position_array, neighborhood_subcells_list):
        this_border = self.level2_cell_borders[this_subcell_index]
        this_north = this_border[0]
        this_south = this_border[1]
        # neighborhood_subcells_list = []
        neighbor_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[tuple(position_array)]
        border = self.level2_cell_borders[neighbor_index]
        neighbor_north = border[0]
        neighbor_south = border[1]
        if neighbor_south <= this_south and neighbor_north >= this_north:
            neighborhood_subcells_list.append(position_array)
        elif neighbor_south < this_south < neighbor_north:
            neighborhood_subcells_list.append(position_array)
        elif neighbor_south < this_north < neighbor_north:
            neighborhood_subcells_list.append(position_array)
        elif neighbor_south >= this_south and neighbor_north <= this_north:
            neighborhood_subcells_list.append(position_array)
        return neighborhood_subcells_list

    def get_north_or_south_neighbor_of_subcell(self, this_subcell_index, position_array, neighborhood_subcells_list):
        this_border = self.level2_cell_borders[this_subcell_index]
        this_west = this_border[2]
        this_east = this_border[3]
        neighbor_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[tuple(position_array)]
        border = self.level2_cell_borders[neighbor_index]
        neighbor_west = border[2]
        neighbor_east = border[3]
        if neighbor_west <= this_west and neighbor_east >= this_east:
            neighborhood_subcells_list.append(position_array)
        elif neighbor_west < this_west < neighbor_east:
            neighborhood_subcells_list.append(position_array)
        elif neighbor_west < this_east < neighbor_east:
            neighborhood_subcells_list.append(position_array)
        elif neighbor_west > this_west and neighbor_east < this_east:
            neighborhood_subcells_list.append(position_array)
        return neighborhood_subcells_list

    #
    def get_adjacent_cells_row_col_dict(self, cell_index1: int, x_bins: np.ndarray, y_bins: np.ndarray):
        x_bin_number = x_bins.size - 1
        y_bin_number = y_bins.size - 1
        x_index = cell_index1 // y_bin_number
        y_index = cell_index1 % y_bin_number
        adjacent_cells = {}
        west_neighbor_x_index = x_index - 1
        east_neighbor_x_index = x_index + 1
        south_neighbor_y_index = y_index - 1
        north_neighbor_y_index = y_index + 1
        # check if neighbor exist in west
        if west_neighbor_x_index >= 0:
            cell_position = np.array([west_neighbor_x_index, y_index])
            adjacent_cells['w'] = cell_position
        else:
            adjacent_cells['w'] = False
        # east
        if east_neighbor_x_index < x_bin_number:
            cell_position = np.array([east_neighbor_x_index, y_index])
            adjacent_cells['e'] = cell_position
        else:
            adjacent_cells['e'] = False
        # south
        if south_neighbor_y_index >= 0:
            cell_position = np.array([x_index, south_neighbor_y_index])
            adjacent_cells['s'] = cell_position
        else:
            adjacent_cells['s'] = False
        # north
        if north_neighbor_y_index < y_bin_number:
            cell_position = np.array([x_index, north_neighbor_y_index])
            adjacent_cells['n'] = cell_position
        else:
            adjacent_cells['n'] = False
        return adjacent_cells

    # this function get index array by x point array and y point array
    # def calculate_level2_index_array_by_point_array(self, x_point_array: np.ndarray, y_point_array: np.ndarray,
    #                                                 trajectory_level1_index_array: np.ndarray):
    #     general_tool1 = GeneralTools()
    #     point_number = x_point_array.shape[0]
    #     index_array = np.zeros(point_number, dtype=int) - 1
    #     large_cell_set = np.unique(trajectory_level1_index_array)
    #     for big_cell_index in large_cell_set:
    #         in_index = (
    #                 trajectory_level1_index_array == big_cell_index)  # 找到trajectory_level1_index_array数组中值等于big_cell_index的布尔数组
    #         x_in_array = x_point_array[in_index]
    #         y_in_array = y_point_array[in_index]
    #         level2_x_bin = self.level2_x_bin_dict[big_cell_index]
    #         level2_y_bin = self.level2_y_bin_dict[big_cell_index]
    #         row_position_in_small_cell = general_tool1.get_bin_index(x_in_array, level2_x_bin, outlier_handling='label')
    #         col_position_in_small_cell = general_tool1.get_bin_index(y_in_array, level2_y_bin, outlier_handling='label')
    #         index_array_array = np.zeros(row_position_in_small_cell.size, dtype=int)
    #         for i in range(row_position_in_small_cell.size):
    #             x_p = row_position_in_small_cell[i]
    #             y_p = col_position_in_small_cell[i]
    #             small_cell_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[
    #                 (big_cell_index, x_p, y_p)]
    #             index_array_array[i] = small_cell_index
    #         index_array[in_index] = index_array_array  # 修改in_index中值为true的内容
    #     return index_array

    def calculate_level2_index_array_by_point_array(self, x_point_array: np.ndarray, y_point_array: np.ndarray,
                                                    trajectory_level1_index_array: np.ndarray, trajectory_index: int,
                                                    interp=True):
        general_tool1 = GeneralTools()
        point_number = x_point_array.shape[0]
        index_array = np.zeros(point_number, dtype=int) - 1
        large_cell_set = np.unique(trajectory_level1_index_array)
        for big_cell_index in large_cell_set:
            in_index = (
                    trajectory_level1_index_array == big_cell_index)  # 找到trajectory_level1_index_array数组中值等于big_cell_index的布尔数组
            x_in_array = x_point_array[in_index]
            y_in_array = y_point_array[in_index]
            level2_x_bin = self.level2_x_bin_dict[big_cell_index]
            level2_y_bin = self.level2_y_bin_dict[big_cell_index]
            row_position_in_small_cell = general_tool1.get_bin_index(x_in_array, level2_x_bin, outlier_handling='label')
            col_position_in_small_cell = general_tool1.get_bin_index(y_in_array, level2_y_bin, outlier_handling='label')
            index_array_array = np.zeros(row_position_in_small_cell.size, dtype=int)
            for i in range(row_position_in_small_cell.size):
                x_p = row_position_in_small_cell[i]
                y_p = col_position_in_small_cell[i]
                small_cell_index = self.level2_cell_outer_index_and_inner_row_col_to_index_dict[
                    (big_cell_index, x_p, y_p)]
                index_array_array[i] = small_cell_index
            index_array[in_index] = index_array_array  # 修改in_index中值为true的内容
        # if interp:
        #     index_array = self.interp_level2_index_array(index_array)
        # self.is_adjectent(index_array,trajectory_index)
        return index_array

    def interp_level2_index_array(self, index_array):
        final_array = [index_array[0]]
        for i in range(len(index_array) - 1):
            current_index = index_array[i]
            next_index = index_array[i + 1]
            if next_index in self.subcell_neighbors_real_level2_index[current_index]:
                final_array.append(next_index)
            elif current_index == next_index:
                final_array.append(next_index)
            else:
                interp_path = nx.dijkstra_path(self.distance_network, source=current_index,
                                               target=next_index)
                interp_path = interp_path[1:]
                final_array.extend(interp_path)
        return final_array

    # this function calculates subcell index array for every trajectory
    def calculate_levle2_index_array_for_set(self, trajectory_set1: TrajectorySet):
        trajectory_number = trajectory_set1.get_trajectory_number()
        for trajectory_index in range(trajectory_number):
            trajectory1 = trajectory_set1.give_trajectory_by_index(trajectory_index)
            # self.calculate_index_array_for_trajectory(trajectory1)
            point_array = trajectory1.real_point_trajectory
            trajectory_level1_index_array = trajectory1.trajectory_level1_cell_index_array
            x_point_array = point_array[:, 0]
            y_point_array = point_array[:, 1]
            index_array = self.calculate_level2_index_array_by_point_array(x_point_array, y_point_array,
                                                                           trajectory_level1_index_array,
                                                                           trajectory_index)
            trajectory1.trajectory_level2_index_sequence = index_array
            trajectory1.after_interp_point_number = len(index_array)

    def init_network(self):
        central_point_gps_array = self.level2_cell_central_points()
        for state_index in range(self.subcell_number):
            neighbors = self.subcell_neighbors_real_level2_index[state_index]
            for neighbor_index in neighbors:
                distance = self.distance_of_central_points(central_point_gps_array, state_index, neighbor_index)
                self.distance_network.add_edge(state_index, neighbor_index, weight=distance)

    def distance_of_central_points(self, central_points_gps, state_index1, state_index2):
        state1_central_point_gps = central_points_gps[state_index1]
        state2_central_point_gps = central_points_gps[state_index2]
        displacement = state1_central_point_gps - state2_central_point_gps
        displacement_square = displacement ** 2
        distance = np.sqrt(np.sum(displacement_square))
        return distance

    #
    def level2_cell_central_points(self):
        cell_number = self.subcell_number
        central_points_gps = np.zeros((cell_number, 2)) - 1
        for i in range(cell_number):
            real_subcell_borders = self.level2_cell_borders[i, :]
            north = real_subcell_borders[0]
            south = real_subcell_borders[1]
            west = real_subcell_borders[2]
            east = real_subcell_borders[3]
            central_latitude = (north + south) / 2
            central_longitude = (west + east) / 2
            central_points_gps[i, 0] = central_latitude
            central_points_gps[i, 1] = central_longitude
        return central_points_gps

    #
    def non_repeat_large_cell_array_from_shortest_path(self, subcell_array):
        gt1 = GeneralTools()
        large_cell_array = self.subcell_index_to_large_cell_index_dict[subcell_array]
        non_repeat_array = gt1.unrepeated_int_array(large_cell_array)[0]
        return non_repeat_array

    #
    def large_neighbor_or_same_by_subcell_index(self, subcell1, subcell2):
        subcell_to_large_dict = self.subcell_index_to_large_cell_index_dict
        large1 = int(subcell_to_large_dict[subcell1])
        large2 = int(subcell_to_large_dict[subcell2])
        large1_position = self.level1_cell_index_to_row_col_array[large1, :]
        large2_position = self.level1_cell_index_to_row_col_array[large2, :]
        distance = np.abs(large1_position[0] - large2_position[0]) + np.abs(large1_position[1] - large2_position[1])
        if distance == 0:
            return 'same'
        elif distance == 1:
            return True
        else:
            return False

    #
    def add_neighbors_to_distribution(self, original_distribution, indicator=1):

        result_distribution = cop.deepcopy(original_distribution)
        print()
        neighbors_list = []
        for i in range(original_distribution.shape[0]):
            for j in range(original_distribution.shape[1]):
                if original_distribution[i, j] > 0:
                    neighbors_of_row_state = self.subcell_neighbors_real_level2_index[i]
                    neighbors_of_col_state = self.subcell_neighbors_real_level2_index[j]
                    for nei_state in neighbors_of_row_state:
                        neighbors_list.append((nei_state, j))
                    for nei_state in neighbors_of_col_state:
                        neighbors_list.append((i, nei_state))
        for distribution_neighbor_pairs in neighbors_list:
            row_index = distribution_neighbor_pairs[0]
            col_index = distribution_neighbor_pairs[1]
            result_distribution[row_index, col_index] = indicator
        return result_distribution



    def init_grid(self, trajectory_set1: TrajectorySet) -> None:
        cc1 = self.cc
        total_epsilon = cc1.total_epsilon
        print("隐私预算：", total_epsilon)
        level1_epsilon_partition = cc1.epsilon_partition[0]
        level1_epsilon = total_epsilon * level1_epsilon_partition
        self.calculate_border(trajectory_set1)
        self.calculate_point_number(trajectory_set1)
        self.level1_divide()  # 计算出一级网格的边界和x轴y轴的bin和一级网格的cell数量
        self.level1_cells()  # 记录网格中每个cell的四面GPS位置和cell的编号（x,y）
        self.level1_trajectory_set_point_to_cell(trajectory_set1)
        self.level1_density(trajectory_set1)
        self.noisy_frequency(level1_epsilon)  # 计算出上面的加噪版
        self.subdividing()
        self.construct_neighbors_real_level2_index()
        self.init_network()
        self.calculate_levle2_index_array_for_set(trajectory_set1)  # 计算出每个点在level2网格中的索引
        self.give_interp_and_unique_sequence(trajectory_set1)
        self.calculate_level_fisrt_node_data(trajectory_set1)

    def give_interp_and_unique_sequence(self, trajectory_set1: TrajectorySet) -> None:
        gt1 = GeneralTools()
        trajectory_number = trajectory_set1.get_trajectory_number()
        for trajectory_index in range(trajectory_number):
            trajectory1 = trajectory_set1.give_trajectory_by_index(trajectory_index)
            index_array = trajectory1.trajectory_level2_index_sequence
            unrepeated_index_array = gt1.unrepeated_int_array(index_array)[0]
            unrepeated_index_array = self.interp_level2_index_array(unrepeated_index_array)
            unrepeated_index_array = np.asarray(unrepeated_index_array, dtype=int)
            trajectory1.after_interp_level2_unique_index_sequence = unrepeated_index_array

    def calculate_level_fisrt_node_data(self, trajectory_set1: TrajectorySet) -> None:
        self.level_fisrt_node_value = np.zeros(self.subcell_number)
        trajectory_number = trajectory_set1.get_trajectory_number()
        for trajectory_index in range(trajectory_number):
            trajectory1 = trajectory_set1.give_trajectory_by_index(trajectory_index)
            index_array = trajectory1.after_interp_level2_unique_index_sequence
            length = len(index_array)
            for i in index_array:
                self.level_fisrt_node_value[i] += 1 / length


